import java.util.*;

/**
 * @author ghp
 * @title 电话号码的字母组合
 */
class Solution {

     public static final Map<Character, String> phoneMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return Collections.emptyList();
        }
        List<String> ans = new ArrayList<>(10);
        // 利用回溯，得到所有字母的组合
        backtrack(ans, digits, 0, new StringBuffer());
        return ans;
    }

    /**
     * 回溯
     *
     * @param ans 所有字母的组合
     * @param digits 输入的数字
     * @param step 当前遍历的深度
     * @param sb 用于拼接字符
     */
    private void backtrack(List<String> ans, String digits, int step, StringBuffer sb) {
        if (step == digits.length()){
            // 已经遍历到最后一层了，结束递归
            ans.add(sb.toString());
            return;
        }
        // 获取当前这一层数字对应的字母
        char digit = digits.charAt(step);
        String letters = phoneMap.get(digit);
        for (int i = 0; i < letters.length(); i++) {
            // 获取当前层的字母
            sb.append(letters.charAt(i));
            // 递归获取下一层的字母
            backtrack(ans, digits, step+1, sb);
            // 恢复现场，用于回溯
            sb.deleteCharAt(step);
        }
    }
}
